#leetcode题目23：合并k个链表
#难度：困难
#时间复杂度：O(nlogk)
#空间复杂度：O(logk)
#方法：分治法
from datetime import MAXYEAR
from typing import List
from typing import List
class ListNode:
    def __init__(self, data):
        self.val = data
        self.next = None
#TODO 链表类，注意在leetcode中没有这个，纯粹是acm模式下才需要这个
class LinkList:
    def __init__(self):
        self.head = None

    def initList(self, data):
        if not data:
            return None
        
        # 创建头结点
        self.head = ListNode(data[0])
        r = self.head
        p = self.head
        
        # 逐个为 data 内的数据创建结点,建立链表
        for i in data[1:]:
            node = ListNode(i)
            p.next = node
            p = p.next
        return r

    def printlist(self, head):
        if head == None:
            return
        node = head
        while node != None:
            print(node.val, end=' ')
            node = node.next
        print()  # 换行


#核心解法
#TODO 暂时没看，后续再补
import heapq #堆


class MyListNode:
    def __init__(self, l:ListNode):
        self.l=l
    def __eq__(self, other):
        return self.l.val == other.l.val
    def __lt__(self, other):
        return self.l.val < other.l.val

class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        dummy=ListNode(0)
        cur=dummy
        heap=[MyListNode(node) for node in lists if node]
        heapq.heapify(heap)
        while heap:
            node=heapq.heappop(heap).l
            cur.next=ListNode(node.val)
            cur=cur.next
            if node.next:
                heapq.heappush(heap,MyListNode(node.next))
        return dummy.next


   


        

#测试数据
lists=[[1,4,5],[1,3,4],[2,6]]
lists_=[LinkList().initList(i) for i in lists]
#预期输出：[1,1,2,3,4,4,5,6]
solution=Solution()
LinkList().printlist(solution.mergeKLists(lists_))

